import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-08-01
 * Time: 20:06
 */
class Solution28 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length,maxVal = 0,maxCount = 0,index = 0;
        int[] ret = new int[n];
        Map<Integer,Integer> hash = new HashMap<>();

        for(int x : barcodes) {
            hash.put(x,hash.getOrDefault(x,0)+1);
            if(maxCount < hash.get(x)) {
                maxVal = x;
                maxCount = hash.get(x);
            }
        }

        // 先处理最多的那个数
        for(int i = 0; i < maxCount; i++) {
            ret[index] = maxVal;
            index += 2;
        }

        hash.remove(maxVal);

        for(int x : hash.keySet()) {
            for(int i = 0; i < hash.get(x); i++) {
                if(index >= n) {
                    index = 1;
                }
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
    }
}
